package com.leetcode.array;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import javax.swing.plaf.basic.BasicBorders.MarginBorder;

import org.junit.Test;

/**
 * Given a m x n matrix, if an element is 0, 
 * set its entire row and column to 0. Do it in place
 * 
 * Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
 * @author Adiy
 *
 */
public class SetMatrixZeroes {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		int n=in.nextInt();
		int[][] nums=new int[m][n];
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				nums[i][j]=in.nextInt();
			}
		}

		setZeroes(nums);
		for(int i=0;i<nums.length;i++){
			for(int j=0;j<nums[0].length;j++){
				System.out.print(nums[i][j]+" ");
			}
			System.out.println();
		}
	}
    public static void setZeroes(int[][] matrix) {
        int lenr=matrix.length;
        int lenc=matrix[0].length;
        System.out.println(lenr+","+lenc);
        List<Integer> setr=new ArrayList<Integer>();
        List<Integer> setc=new ArrayList<Integer>();
        int multi=1;
        for(int i=0;i<lenr;i++){
        	multi=1;
        	for(int j=0;j<lenc;j++){
        		if((multi<<matrix[i][j])==0||multi*matrix[i][j]==0){
        			setr.add(i);
        		}
        	}
        }
        
        for(int j=0;j<lenc;j++){
        	multi=1;
        	for(int i=0;i<lenr;i++){
        		if((multi<<matrix[i][j])==0||multi*matrix[i][j]==0){
        			setc.add(j);
        		}
        	}
        }
        
        for(int i=0;i<lenr;i++){
        	if(setr.contains(i)){
        		for(int j=0;j<lenc;j++){
        			matrix[i][j]=0;
        		}
        	}
        }
        for(int j=0;j<lenc;j++){
        	if(setc.contains(j)){
        		for(int i=0;i<lenr;i++){
        			matrix[i][j]=0;
        		}
        	}
        }
    }
    
    @Test
    public void fun(){
    	int i=-2147483648;
    	int j=2147483647;
    	System.out.println(i+","+2*i);
    	System.out.println(j+","+2*j);
    }
}
